package com.fw.leetcode.stack;

import com.fw.leetcode.LeetCode;

import java.util.ArrayDeque;

/**
 * 402. Remove K Digits
 *
 * Given string num representing a non-negative integer num, and an integer k, return the
 * smallest possible integer after removing k digits from num.
 *
 * Example 1:
 *  Input: num = "1432219", k = 3
 *  Output: "1219"
 *  Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
 *
 * Example 2:
 *  Input: num = "10200", k = 1
 *  Output: "200"
 *  Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
 *
 * Example 3:
 *  Input: num = "10", k = 2
 *  Output: "0"
 *  Explanation: Remove all the digits from the number and it is left with nothing which is 0.
 *
 * Constraints:
 *  1 <= k <= num.length <= 10^5
 *  num consists of only digits.
 *  num does not have any leading zeros except for the zero itself.
 */
public class Num_0402 implements LeetCode {
    private interface Solution {
        String removeKdigits(String num, int k);

        default void assertEquals(String num, int k, String expected) {
            if (!expected.equals(removeKdigits(num, k))) {
                removeKdigits(num, k);
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public String removeKdigits(String num, int k) { // 贪心 + 单调栈：时O(n) 空O(n)
            /*
             * 移出k位数字（构成最小值）
             * - 观察到数字大小的起伏变化
             * num = "1432219", k = 3 => "1219"
             * 1) 1        => 压栈 1
             * 2) 4,1      => 4 > 1 压栈 4
             * 3) 3,1      => 3 < 4 出栈 4 压栈 3
             * 4) 2,1      => 2 < 3 出栈 3 压栈 2
             * 5) 2,2,1    => 2 == 2 压栈 2
             * 6) 1,2,1    => 1 < 2 出栈 2 压栈 1
             * 7) 9,1,2,1  => 9 > 1 压栈 9
             *
             * 一次性全入栈的情况
             * num = "1111111", k = 3 => "1111"
             * num = "1234567", k = 3 => "1234", 栈中 [7,6,5,4,3,2,1] 只取栈底4个
             *
             *
             * num = "2411219", k = 3 => "1119", 栈中 [9,1,1,1,2] 只取栈底4个
             * num = "1411219", k = 3 => "1111", 栈中 [9,1,1,1,1] 只取栈底4个
             * num = "1411219", k = 3 => "1111", 栈中 [9,1,1,1,1] 只取栈底4个
             */
            if (num == null) return "0";
            if (num.length() == k) return "0";
            int removeCnt = k;
            ArrayDeque<Character> deque = new ArrayDeque<>();
            for (int i = 0; i < num.length(); i++) {
                // stack top - - base，比栈顶元素大时，能出栈多少就出栈多少
                while (!deque.isEmpty() && num.charAt(i) < deque.peekFirst() && removeCnt > 0) {
                    deque.removeFirst();
                    removeCnt--;
                }
                deque.addFirst(num.charAt(i));
            }
            while (removeCnt-- > 0) { // 移除多余位
                deque.removeFirst();
            }
            if (deque.isEmpty()) return "0";
            String outNum = "";
            for (int i = 0; i < num.length() - k; i++) {
                char ch = deque.removeLast();
                if (ch == '0' && "".equals(outNum)) {
                    continue;
                }
                outNum += ch;
            }
            if ("".equals(outNum)) return "0";
            return outNum;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertEquals("1432219", 3, "1219");
        solution.assertEquals("1234567", 3, "1234");
        solution.assertEquals("1111111", 3, "1111");
        solution.assertEquals("1411219", 3, "1111");
        solution.assertEquals("2411219", 3, "1119");
        solution.assertEquals("10200", 1, "200");
        solution.assertEquals("10", 2, "0");
        solution.assertEquals("10", 1, "0");
    }
}
